{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Digit Count in Range"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: digitsCount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #范围内的数字计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个在 <code>0</code>&nbsp;到&nbsp;<code>9</code> 之间的整数&nbsp;<code>d</code>，和两个正整数&nbsp;<code>low</code>&nbsp;和&nbsp;<code>high</code>&nbsp;分别作为上下界。返回&nbsp;<code>d</code> 在&nbsp;<code>low</code>&nbsp;和&nbsp;<code>high</code>&nbsp;之间的整数中出现的次数，包括边界&nbsp;<code>low</code> 和&nbsp;<code>high</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>d = 1, low = 1, high = 13\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释： </strong>\n",
    "数字 <code>d=1</code> 在 <code>1,10,11,12,13 中出现 6 次</code>。注意 <code>d=1</code> 在数字 11 中出现两次。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>d = 3, low = 100, high = 250\n",
    "<strong>输出：</strong>35\n",
    "<strong>解释：</strong>\n",
    "数字 <code>d=3</code> 在 <code>103,113,123,130,131,...,238,239,243 出现 35 次。</code>\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li><code>0 &lt;= d &lt;= 9</code></li>\n",
    "\t<li><code>1 &lt;= low &lt;= high &lt;= 2&times;10^8</code></li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [digit-count-in-range](https://leetcode.cn/problems/digit-count-in-range/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [digit-count-in-range](https://leetcode.cn/problems/digit-count-in-range/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n1\\n13', '3\\n100\\n250']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "\n",
    "        def check(n):\n",
    "            s = str(n)\n",
    "            m = len(s)\n",
    "\n",
    "            @cache\n",
    "            def dfs(i, is_limit, is_num, cnt):\n",
    "                if i == m:\n",
    "                    return int(is_num) * cnt\n",
    "                \n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = dfs(i+1, False, False, cnt)\n",
    "\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for x in range(0 if is_num else 1, up + 1):\n",
    "                    new_limit = is_limit and x == up\n",
    "                    new_cnt = cnt + 1 if x == d else cnt\n",
    "                    res += dfs(i+1, new_limit, True, new_cnt)\n",
    "                return res\n",
    "            return dfs(0, True, False, 0)\n",
    "        \n",
    "        return check(high) - check(low-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        \n",
    "        def calc(num, d):\n",
    "            \"\"\"\n",
    "            return the counts of i that have a digit 'd' and 0 < i <= num\n",
    "            \"\"\"\n",
    "            power = 1\n",
    "            res = 0\n",
    "            while power <= num:\n",
    "                high = num //(power*10)\n",
    "                curr = num // power % 10\n",
    "                rmd = num % power\n",
    "                print(high,curr,rmd)\n",
    "                if curr > d:\n",
    "                    res += (high+1)*power  # 0 ~ high\n",
    "                elif curr < d:\n",
    "                    res += high*power   # 0 ~ high-1\n",
    "                else:\n",
    "                    res += high*power + rmd + 1  # 0 ~ high-1 + 0 ~ rmd\n",
    "                if d == 0:\n",
    "                    res -= power\n",
    "                print(res,'num')\n",
    "                power *= 10\n",
    "            return res\n",
    "        return calc(high, d) - calc(low-1, d)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        slow = str(low)\n",
    "        shigh = str(high)\n",
    "\n",
    "        def func(s: str, i: int, cntd: int, is_limit: bool, is_num: bool) -> int: \n",
    "            if i == len(s):\n",
    "                return cntd \n",
    "            if (i, cntd, is_limit, is_num) in cache:\n",
    "                return cache[(i, cntd, is_limit, is_num)]\n",
    "            res = 0 \n",
    "            if is_num == False:\n",
    "                res = func(s, i+1, cntd, False, False)\n",
    "\n",
    "            max_v = int(s[i]) if is_limit else 9\n",
    "            low_v = 0 if is_num else 1\n",
    "            for v in range(low_v, max_v + 1):\n",
    "                res += func(\n",
    "                    s,\n",
    "                    i+1,\n",
    "                    cntd + (v==d),\n",
    "                    is_limit and (v==max_v),\n",
    "                    True  # i+1前的数位填数字了 \n",
    "                )\n",
    "            cache[(i, cntd, is_limit, is_num)] = res \n",
    "            return res \n",
    "        \n",
    "        lowcount = 0\n",
    "        for c in slow:\n",
    "            if c == str(d):\n",
    "                lowcount += 1\n",
    "        \n",
    "        cache = {}\n",
    "        count_high = func(shigh, 0, 0, True, False)\n",
    "        cache = {}\n",
    "        count_low = func(slow, 0, 0, True, False)\n",
    "\n",
    "        return count_high - count_low + lowcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        def cal(x):\n",
    "            x = str(x)\n",
    "            n = len(x)\n",
    "\n",
    "            @cache\n",
    "            def f(i, isnum, islimited):\n",
    "                if i == n:\n",
    "                    return [int(isnum), 0]\n",
    "                tot, cntd = 0, 0\n",
    "                if not isnum:\n",
    "                    tot += f(i + 1, False, False)[0]\n",
    "                    cntd += f(i + 1, False, False)[1]\n",
    "                down = 0 if isnum else 1\n",
    "                up = 9 if not islimited else int(x[i])\n",
    "                for k in range(down, up + 1):\n",
    "                    a, b = f(i + 1, True, islimited and k == up)\n",
    "                    tot += a \n",
    "                    if k == d:\n",
    "                        cntd += b + a \n",
    "                    else:\n",
    "                        cntd += b \n",
    "                return [tot, cntd]\n",
    "            \n",
    "            return f(0, False, True)[1]\n",
    "        \n",
    "        return cal(high) - cal(low - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        def solve(s, n, p):\n",
    "            @cache\n",
    "            def f(i, is_limit, is_num, cnt):\n",
    "                if i == n:\n",
    "                    return cnt\n",
    "                res = 0\n",
    "                if is_num == 0:\n",
    "                    res = f(i + 1, False, False, cnt)\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(1 - int(is_num), up + 1):\n",
    "                    res += f(i + 1, is_limit and (d == up), True, cnt + (d == p))\n",
    "                return res\n",
    "            return f(0,True,False, 0) \n",
    "        print(solve(str(10),2,1))     \n",
    "        return solve(str(high),len(str(high)), d)  - solve(str(low - 1),len(str(low - 1)), d)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        @cache  \n",
    "        def f(i: int, is_limit: bool,is_num: bool,s:str,cur:int) -> int:\n",
    "            if i == len(s):\n",
    "                if is_num:\n",
    "                    return cur\n",
    "                return 0\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i + 1,False, False,s,cur)\n",
    "            low = 0 if is_num else 1 \n",
    "            up = int(s[i]) if is_limit else 9  \n",
    "            for dd in range(low, up + 1):  \n",
    "                res += f(i + 1, is_limit and dd == up, True,s,cur + (d == dd))\n",
    "            return res\n",
    "        \n",
    "        return f(0,True,False,str(high),0) - f(0,True,False,str(int(low) - 1),0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        high=str(high)\n",
    "        n=len(high)\n",
    "        low=str(low).rjust(n,'0')\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,k,is_top,is_bottom,is_num):\n",
    "            if i==n:\n",
    "                return k\n",
    "            minv=int(low[i]) if is_bottom else 0\n",
    "            maxv=int(high[i]) if is_top else 9\n",
    "            ans=0\n",
    "            for j in range(minv,maxv+1):\n",
    "                if not is_num and j>0:\n",
    "                    is_num=True\n",
    "                ans+=dfs(i+1,k+(j==d!=0 or j==d==0 and is_num),is_top and j==maxv,is_bottom and j==minv,is_num)\n",
    "            return ans\n",
    "    \n",
    "        return dfs(0,0,True,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        high=str(high)\n",
    "        n=len(high)\n",
    "        low=str(low).rjust(n,'0')\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,k,is_top,is_bottom,is_num):\n",
    "            if i==n:\n",
    "                return k\n",
    "            minv=int(low[i]) if is_bottom else 0\n",
    "            maxv=int(high[i]) if is_top else 9\n",
    "            ans=0\n",
    "            for j in range(minv,maxv+1):\n",
    "                if not is_num and j>0:\n",
    "                    is_num=True\n",
    "                ans+=dfs(i+1,k+(j==d!=0 or j==d==0 and is_num),is_top and j==maxv,is_bottom and j==minv,is_num)\n",
    "            return ans\n",
    "    \n",
    "        return dfs(0,0,True,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, t: int, low: int, high: int) -> int:\n",
    "        def f(s: int) -> int:\n",
    "            s = str(s)\n",
    "            @cache\n",
    "            def f(i: int, cntt: int, is_limit: int, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return cntt\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, cntt, False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                for d in range(low, up + 1):\n",
    "                    res += f(i + 1, cntt + int(d == t), is_limit and d == int(s[i]), True)\n",
    "                return res\n",
    "            return f(0, 0, True, False)\n",
    "        s = str(low)\n",
    "        cnt = 0\n",
    "        for x in s:\n",
    "            if int(x) == t:\n",
    "                cnt += 1\n",
    "        return f(high) - f(low) + cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#范围内的数字计数，输入：d = 1, low = 1, high = 13输出：6\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        def func(n):\n",
    "            nums = [int(x) for x in str(n)]\n",
    "            @cache\n",
    "            def back(wei,cnt,lim,ze):\n",
    "                if wei == len(nums):return cnt\n",
    "                p = 10 if not lim else nums[wei]\n",
    "                res = 0 if not lim else back(wei+1,cnt+(nums[wei]==d),True,False)\n",
    "                if p != 0:\n",
    "                    if ze:res += back(wei+1,cnt,False,True)\n",
    "                    else:res += back(wei+1,cnt+(d==0),False,False)\n",
    "                for i in range(1,p):\n",
    "                    res += back(wei+1,cnt+(i==d),False,False)\n",
    "                return res\n",
    "            return back(0,0,True,True)\n",
    "        if low == 1:return func(high)\n",
    "        else:return func(high)-func(low-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        slow=str(low-1)\n",
    "        shigh=str(high)\n",
    "        @cache\n",
    "        def dfs(sb,i,ss,islimit,isnum):\n",
    "            if i==len(sb):\n",
    "                if isnum:\n",
    "                    return ss\n",
    "                return 0\n",
    "            res=0\n",
    "            if not isnum:\n",
    "                res+=dfs(sb,i+1,ss,False,False)\n",
    "            mi=0 if isnum else 1\n",
    "            ma=int(sb[i]) if islimit else 9\n",
    "            for j in range(mi,ma+1):\n",
    "                res+=dfs(sb,i+1,ss+(j==d),islimit and j==ma,True)\n",
    "            return res\n",
    "        return dfs(shigh,0,0,True,False)-dfs(slow,0,0,True,False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "\n",
    "        def calc(t):\n",
    "            t = str(t)\n",
    "            @cache\n",
    "            def dfs(i, curr, isLimit, isNum):\n",
    "                if i == len(t): return curr if isNum else 0\n",
    "                upper = int(t[i]) if isLimit else 9\n",
    "                lower = 0 if isNum else 1\n",
    "                ans = dfs(i + 1, curr, False, False) if not isNum else 0\n",
    "                for x in range(lower, upper + 1):\n",
    "                    ans += dfs(i + 1, curr + int(x == d), isLimit and x == upper, True)\n",
    "                return ans\n",
    "            return dfs(0, 0, True, False)\n",
    "        # print(calc(int(high)), calc(int(low) - 1))\n",
    "        return calc(int(high)) - calc(int(low) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        def solve(s, n, p):\n",
    "            @cache\n",
    "            def f(i, is_limit, is_num, cnt):\n",
    "                if i == n:\n",
    "                    return cnt\n",
    "                res = 0\n",
    "                if is_num == 0:\n",
    "                    res = f(i + 1, False, False, cnt)\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(1 - int(is_num), up + 1):\n",
    "                    res += f(i + 1, is_limit and (d == up), True, cnt + (d == p))\n",
    "                return res\n",
    "            return f(0,True,False, 0) \n",
    "        print(solve(str(10),2,1))     \n",
    "        return solve(str(high),len(str(high)), d)  - solve(str(low - 1),len(str(low - 1)), d)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "\n",
    "        def check(n):\n",
    "            s = str(n)\n",
    "            m = len(s)\n",
    "\n",
    "            # i: 第几位\n",
    "            # is_limit: 当前第i位是否顶到上界\n",
    "            @cache\n",
    "            def dfs(i, is_limit, is_num, cnt):\n",
    "                if i == m:\n",
    "                    return cnt if is_num else 0\n",
    "                \n",
    "                res = 0\n",
    "                if not is_num: # 如果目前没有填数，可以跳过该位\n",
    "                    res = dfs(i+1, False, False, cnt)\n",
    "\n",
    "                up = int(s[i]) if is_limit else 9 # 下一位的最大值，如果是顶到上边界，就只能取当前值，否则可以取最大值9\n",
    "                start = 0 if is_num else 1 # 当前没填数，下一个就不能从0开始（处理前导零）\n",
    "                for x in range(start, up + 1):\n",
    "                    new_limit = is_limit and x == up\n",
    "                    new_cnt = cnt + 1 if x == d else cnt\n",
    "                    res += dfs(i+1, new_limit, True, new_cnt)\n",
    "                return res\n",
    "            return dfs(0, True, False, 0)\n",
    "        \n",
    "        return check(high) - check(low-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        def cal(n: int) -> int:\n",
    "            s = str(n)\n",
    "            @cache  # 记忆化搜索\n",
    "            def f(i: int, cnt: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == len(s):\n",
    "                    return int(is_num) * cnt  # is_num 为 True 表示得到了一个合法数字\n",
    "                res = 0\n",
    "                if not is_num:  # 可以跳过当前数位\n",
    "                    res = f(i + 1, cnt, False, False)\n",
    "                low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "                up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "                for digit in range(low, up + 1):  # 枚举要填入的数字 digit\n",
    "                    res += f(i + 1, cnt + (digit == d), is_limit and digit == up, True)\n",
    "                return res\n",
    "            return f(0, 0, True, False)\n",
    "\n",
    "        return cal(high) - cal(low - 1)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "\n",
    "        def f(s):\n",
    "            @cache\n",
    "            def dfs(i,cnt,is_num,is_limit):\n",
    "                if i == len(s):\n",
    "                    return cnt if is_num else 0\n",
    "                ans = 0\n",
    "                if not is_num:\n",
    "                    ans = dfs(i + 1,cnt,False,False)\n",
    "                down = 0 if is_num else 1\n",
    "                up = 9 if not is_limit else int(s[i])\n",
    "                for j in range(down,up + 1):\n",
    "                    ans += dfs(i + 1,cnt +int(j == d),True,is_limit and j == up)\n",
    "                return ans\n",
    "            return dfs(0,0,False,True)\n",
    "        \n",
    "        return f(str(high)) - f(str(low - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        low = str(low - 1)\n",
    "        high = str(high)\n",
    "        @cache\n",
    "        def dfs(i, cnt, is_limit, is_num, s):\n",
    "            if i == len(s):\n",
    "                return cnt\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += dfs(i + 1, cnt, False, False, s)\n",
    "            bottom = 0 if is_num else 1\n",
    "            top = int(s[i]) if is_limit else 9\n",
    "            for x in range(bottom, top + 1):\n",
    "                res += dfs(i + 1, cnt + (d == x), is_limit and x == top, True, s)\n",
    "            return res\n",
    "        return dfs(0, 0, True, False, high) - dfs(0, 0, True, False, low)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        high=str(high)\n",
    "        n=len(high)\n",
    "        low=str(low).rjust(n,'0')\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,k,is_top,is_bottom,is_num):\n",
    "            if i==n:\n",
    "                return k\n",
    "            minv=int(low[i]) if is_bottom else 0\n",
    "            maxv=int(high[i]) if is_top else 9\n",
    "            ans=0\n",
    "            for j in range(minv,maxv+1):\n",
    "                if not is_num and j>0:\n",
    "                    is_num=True\n",
    "                ans+=dfs(i+1,k+(j==d!=0 or j==d==0 and is_num),is_top and j==maxv,is_bottom and j==minv,is_num)\n",
    "            return ans\n",
    "    \n",
    "        return dfs(0,0,True,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        slow = str(low)\n",
    "        shigh = str(high)\n",
    "\n",
    "        def func(s: str, i: int, cntd: int, is_limit: bool, is_num: bool) -> int: \n",
    "            if i == len(s):\n",
    "                return cntd \n",
    "            if (i, cntd, is_limit, is_num) in cache:\n",
    "                return cache[(i, cntd, is_limit, is_num)]\n",
    "            res = 0 \n",
    "            if is_num == False:\n",
    "                res = func(s, i+1, cntd, False, False)\n",
    "\n",
    "            max_v = int(s[i]) if is_limit else 9\n",
    "            low_v = 0 if is_num else 1\n",
    "            for v in range(low_v, max_v + 1):\n",
    "                res += func(\n",
    "                    s,\n",
    "                    i+1,\n",
    "                    cntd + (v==d),\n",
    "                    is_limit and (v==max_v),\n",
    "                    True  # i+1前的数位填数字了 \n",
    "                )\n",
    "            cache[(i, cntd, is_limit, is_num)] = res \n",
    "            return res \n",
    "        \n",
    "        lowcount = 0\n",
    "        for c in slow:\n",
    "            if c == str(d):\n",
    "                lowcount += 1\n",
    "        \n",
    "        cache = {}\n",
    "        count_high = func(shigh, 0, 0, True, False)\n",
    "        cache = {}\n",
    "        count_low = func(slow, 0, 0, True, False)\n",
    "\n",
    "        return count_high - count_low + lowcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        slow = str(low)\n",
    "        shigh = str(high)\n",
    "\n",
    "        def func(s: str, i: int, cntd: int, is_limit: bool, is_num: bool) -> int: \n",
    "            if i == len(s):\n",
    "                return cntd \n",
    "            if (i, cntd, is_limit, is_num) in cache:\n",
    "                return cache[(i, cntd, is_limit, is_num)]\n",
    "            \n",
    "            res = 0 \n",
    "            if is_num == False:\n",
    "                res = func(s, i+1, cntd, False, False)\n",
    "\n",
    "            max_v = int(s[i]) if is_limit else 9\n",
    "            low_v = 0 if is_num else 1\n",
    "            for v in range(low_v, max_v + 1):\n",
    "                res += func(\n",
    "                    s,\n",
    "                    i+1,\n",
    "                    cntd + (v==d),\n",
    "                    is_limit and (v==max_v),\n",
    "                    True  # i+1前的数位填数字了 \n",
    "                )\n",
    "            cache[(i, cntd, is_limit, is_num)] = res \n",
    "            return res \n",
    "        \n",
    "        lowcount = 0\n",
    "        for c in slow:\n",
    "            if c == str(d):\n",
    "                lowcount += 1\n",
    "        \n",
    "        cache = {}\n",
    "        count_high = func(shigh, 0, 0, True, False)\n",
    "        cache = {}\n",
    "        count_low = func(slow, 0, 0, True, False)\n",
    "\n",
    "        return count_high - count_low + lowcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        low = str(low - 1)\n",
    "        high = str(high)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def f(i: int, cnt: int, is_limit: bool, is_num: bool, s: str) -> int:\n",
    "            if i == len(s):\n",
    "                return cnt\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += f(i + 1, cnt, False, False, s)\n",
    "            top = int(s[i]) if is_limit else 9\n",
    "            bot = 0 if is_num else 1\n",
    "            for x in range(bot, top + 1):\n",
    "                res += f(i + 1, cnt + (1 if x == d else 0), is_limit and x == top, True, s)\n",
    "            return res\n",
    "\n",
    "        return f(0, 0, True, False, high) - f(0, 0, True, False, low)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        def calc(t):\n",
    "            t = str(t)\n",
    "            @cache\n",
    "            def dfs(i, curr, isLimit, isNum):\n",
    "                if i == len(t): return curr if isNum else 0\n",
    "                upper = int(t[i]) if isLimit else 9\n",
    "                lower = 0 if isNum else 1\n",
    "                ans = dfs(i + 1, curr, False, False) if not isNum else 0\n",
    "                for x in range(lower, upper + 1):\n",
    "                    ans += dfs(i + 1, curr + int(x == d), isLimit and x == upper, True)\n",
    "                return ans\n",
    "            return dfs(0, 0, True, False)\n",
    "        return calc(int(high)) - calc(int(low) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        def calc(t):\n",
    "            t = str(t)\n",
    "            @cache\n",
    "            def dfs(i, curr, isLimit, isNum):\n",
    "                if i == len(t): return curr if isNum else 0\n",
    "                upper = int(t[i]) if isLimit else 9\n",
    "                lower = 0 if isNum else 1\n",
    "                ans = dfs(i + 1, curr, False, False) if not isNum else 0\n",
    "                for x in range(lower, upper + 1):\n",
    "                    ans += dfs(i + 1, curr + int(x == d), isLimit and x == upper, True)\n",
    "                return ans\n",
    "            return dfs(0, 0, True, False)\n",
    "        return calc(int(high)) - calc(int(low) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        high=str(high)\n",
    "        n=len(high)\n",
    "        low=str(low).rjust(n,'0')\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,k,is_top,is_bottom,is_num):\n",
    "            if i==n:\n",
    "                return k\n",
    "            minv=int(low[i]) if is_bottom else 0\n",
    "            maxv=int(high[i]) if is_top else 9\n",
    "            ans=0\n",
    "            for j in range(minv,maxv+1):\n",
    "                if not is_num and j>0:\n",
    "                    is_num=True\n",
    "                ans+=dfs(i+1,k+(j==d!=0 or j==d==0 and is_num),is_top and j==maxv,is_bottom and j==minv,is_num)\n",
    "            return ans\n",
    "    \n",
    "        return dfs(0,0,True,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        ## 返回在0~n之间，数字d出现的次数\n",
    "        def helper(d,n):\n",
    "            @cache\n",
    "            def f(i,cntd,is_limit, is_num):\n",
    "                nonlocal s, d\n",
    "                if i == len(s):\n",
    "                    return cntd\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res += f(i+1, 0, False, False)\n",
    "                down = 1 - int(is_num)\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for digit in range(down, up+1):\n",
    "                    res += f(i+1, cntd+(1 if digit == d else 0), is_limit and digit == up, True)\n",
    "                return res\n",
    "            s = str(n)\n",
    "            return f(0,0, True, False)\n",
    "\n",
    "        return helper(d,high) - helper(d,low-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        high=str(high)\n",
    "        n=len(high)\n",
    "        low=str(low).rjust(n,'0')\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,k,is_top,is_bottom,is_num):\n",
    "            if i==n:\n",
    "                return k\n",
    "            minv=int(low[i]) if is_bottom else 0\n",
    "            maxv=int(high[i]) if is_top else 9\n",
    "            ans=0\n",
    "            for j in range(minv,maxv+1):\n",
    "                if not is_num and j>0:\n",
    "                    is_num=True\n",
    "                ans+=dfs(i+1,k+(j==d!=0 or j==d==0 and is_num),is_top and j==maxv,is_bottom and j==minv,is_num)\n",
    "            return ans\n",
    "    \n",
    "        return dfs(0,0,True,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        slow = str(low)\n",
    "        shigh = str(high)\n",
    "\n",
    "        @lru_cache\n",
    "        def func(s: str, i: int, cntd: int, is_limit: bool, is_num: bool) -> int: \n",
    "            if i == len(s):\n",
    "                return cntd # * int(is_num)\n",
    "            \n",
    "            res = 0 \n",
    "            if is_num == False:\n",
    "                res = func(s, i+1, cntd, False, False)\n",
    "\n",
    "            max_v = int(s[i]) if is_limit else 9\n",
    "            low_v = 0 if is_num else 1\n",
    "            for v in range(low_v, max_v + 1):\n",
    "                res += func(\n",
    "                    s,\n",
    "                    i+1,\n",
    "                    cntd + (v==d),\n",
    "                    is_limit and (v==max_v),\n",
    "                    True  # i+1前的数位填数字了 \n",
    "                )\n",
    "            return res \n",
    "        \n",
    "        lowcount = 0\n",
    "        for c in slow:\n",
    "            if c == str(d):\n",
    "                lowcount += 1\n",
    "\n",
    "        return func(shigh, 0, 0, True, False) - func(slow, 0, 0, True, False) + lowcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        high=str(high)\n",
    "        n=len(high)\n",
    "        low=str(low).rjust(n,'0')\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,k,is_top,is_bottom,is_num):\n",
    "            if i==n:\n",
    "                return k\n",
    "            minv=int(low[i]) if is_bottom else 0\n",
    "            maxv=int(high[i]) if is_top else 9\n",
    "            ans=0\n",
    "            for j in range(minv,maxv+1):\n",
    "                if not is_num and j>0:\n",
    "                    is_num=True\n",
    "                ans+=dfs(i+1,k+(j==d!=0 or j==d==0 and is_num),is_top and j==maxv,is_bottom and j==minv,is_num)\n",
    "            return ans\n",
    "    \n",
    "        return dfs(0,0,True,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        slow = str(low)\n",
    "        shigh = str(high)\n",
    "\n",
    "        @lru_cache\n",
    "        def func(s: str, i: int, cntd: int, is_limit: bool, is_num: bool) -> int: \n",
    "            if i == len(s):\n",
    "                return cntd # * int(is_num)\n",
    "            \n",
    "            res = 0 \n",
    "            if is_num == False:\n",
    "                res = func(s, i+1, cntd, False, False)\n",
    "\n",
    "            max_v = int(s[i]) if is_limit else 9\n",
    "            low_v = 0 if is_num else 1\n",
    "            for v in range(low_v, max_v + 1):\n",
    "                res += func(\n",
    "                    s,\n",
    "                    i+1,\n",
    "                    cntd + (v==d),\n",
    "                    is_limit and (v==max_v),\n",
    "                    True  # i+1前的数位填数字了 \n",
    "                )\n",
    "            return res \n",
    "        \n",
    "        lowcount = 0\n",
    "        for c in slow:\n",
    "            if c == str(d):\n",
    "                lowcount += 1\n",
    "\n",
    "        return func(shigh, 0, 0, True, False) - func(slow, 0, 0, True, False) + lowcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        high=str(high)\n",
    "        n=len(high)\n",
    "        low=str(low).rjust(n,'0')\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,k,is_top,is_bottom,is_num):\n",
    "            if i==n:\n",
    "                return k\n",
    "            minv=int(low[i]) if is_bottom else 0\n",
    "            maxv=int(high[i]) if is_top else 9\n",
    "            ans=0\n",
    "            for j in range(minv,maxv+1):\n",
    "                if not is_num and j>0:\n",
    "                    is_num=True\n",
    "                ans+=dfs(i+1,k+(j==d!=0 or j==d==0 and is_num),is_top and j==maxv,is_bottom and j==minv,is_num)\n",
    "            return ans\n",
    "    \n",
    "        return dfs(0,0,True,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        @cache  \n",
    "        def f(i: int, is_limit: bool,is_num: bool,s:str,tag:int) -> int:\n",
    "            if i == len(s):\n",
    "                if is_num:\n",
    "                    return tag\n",
    "                return 0\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i + 1,False, False,s,tag)\n",
    "            low = 0 if is_num else 1 \n",
    "            up = int(s[i]) if is_limit else 9  \n",
    "            for t in range(low, up + 1):  \n",
    "                res += f(i + 1, is_limit and t == up, True,s,tag + (t == d))\n",
    "            return res\n",
    "        \n",
    "        return f(0,True,False,str(high),0) - f(0,True,False,str(int(low) - 1),0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#范围内的数字计数，输入：d = 1, low = 1, high = 13输出：6；输入：d = 3, low = 100, high = 250,输出：35\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        def func(n):\n",
    "            nums = [int(x) for x in str(n)]\n",
    "            @cache\n",
    "            def back(wei,cnt,lim,ze):\n",
    "                if wei == len(nums):return cnt\n",
    "                p = 10 if not lim else nums[wei]\n",
    "                res = 0 if not lim else back(wei+1,cnt+(nums[wei]==d),True,False)\n",
    "                if p != 0:\n",
    "                    if ze:res += back(wei+1,cnt,False,True)\n",
    "                    else:res += back(wei+1,cnt+(d==0),False,False)\n",
    "                for i in range(1,p):\n",
    "                    res += back(wei+1,cnt+(i==d),False,False)\n",
    "                return res\n",
    "            return back(0,0,True,True)\n",
    "        if low == 1:return func(high)\n",
    "        else:return func(high)-func(low-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        slow = str(low)\n",
    "        shigh = str(high)\n",
    "\n",
    "        @lru_cache\n",
    "        def func(s: str, i: int, cntd: int, is_limit: bool, is_num: bool) -> int: \n",
    "            if i == len(s):\n",
    "                return cntd # * int(is_num)\n",
    "            \n",
    "            res = 0 \n",
    "            if is_num == False:\n",
    "                res = func(s, i+1, cntd, False, False)\n",
    "\n",
    "            max_v = int(s[i]) if is_limit else 9\n",
    "            low_v = 0 if is_num else 1\n",
    "            for v in range(low_v, max_v + 1):\n",
    "                res += func(\n",
    "                    s,\n",
    "                    i+1,\n",
    "                    cntd + (v==d),\n",
    "                    is_limit and (v==max_v),\n",
    "                    True  # i+1前的数位填数字了 \n",
    "                )\n",
    "            return res \n",
    "        \n",
    "        lowcount = 0\n",
    "        for c in slow:\n",
    "            if c == str(d):\n",
    "                lowcount += 1\n",
    "\n",
    "        return func(shigh, 0, 0, True, False) - func(slow, 0, 0, True, False) + lowcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, x: int, low: int, high: int) -> int:\n",
    "        def cal(s):\n",
    "            @cache\n",
    "            def dfs(i, cnt, is_limit, is_num):\n",
    "                if i == len(s): \n",
    "                    if is_num:\n",
    "                        return cnt \n",
    "                    else:\n",
    "                        return 0\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res = dfs(i + 1, cnt, False, False)\n",
    "                low = 0 if is_num else 1\n",
    "                up = int(s[i]) if is_limit else 9\n",
    "                for d in range(low, up + 1):\n",
    "                    res += dfs(i + 1, cnt + (d == x), is_limit and d == up, True)\n",
    "                return res\n",
    "            return dfs(0, 0, True, False)\n",
    "        return cal(str(high)) - cal(str(int(low) - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        slow = str(low)\n",
    "        shigh = str(high)\n",
    "\n",
    "        @lru_cache\n",
    "        def func(s: str, i: int, cntd: int, is_limit: bool, is_num: bool) -> int: \n",
    "            if i == len(s):\n",
    "                return cntd \n",
    "            \n",
    "            res = 0 \n",
    "            if is_num == False:\n",
    "                res = func(s, i+1, cntd, False, False)\n",
    "\n",
    "            max_v = int(s[i]) if is_limit else 9\n",
    "            low_v = 0 if is_num else 1\n",
    "            for v in range(low_v, max_v + 1):\n",
    "                res += func(\n",
    "                    s,\n",
    "                    i+1,\n",
    "                    cntd + (v==d),\n",
    "                    is_limit and (v==max_v),\n",
    "                    True  # i+1前的数位填数字了 \n",
    "                )\n",
    "            return res \n",
    "        \n",
    "        lowcount = 0\n",
    "        for c in slow:\n",
    "            if c == str(d):\n",
    "                lowcount += 1\n",
    "\n",
    "        return func(shigh, 0, 0, True, False) - func(slow, 0, 0, True, False) + lowcount"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def digitsCount(self, d: int, low: int, high: int) -> int:\n",
    "        slow = str(low)\n",
    "        shigh = str(high)\n",
    "\n",
    "        @lru_cache\n",
    "        def func(s: str, i: int, cntd: int, is_limit: bool, is_num: bool) -> int: \n",
    "            if i == len(s):\n",
    "                return cntd * int(is_num)\n",
    "            \n",
    "            res = 0 \n",
    "            if is_num == False:\n",
    "                res = func(s, i+1, cntd, False, False)\n",
    "\n",
    "            max_v = int(s[i]) if is_limit else 9\n",
    "            low_v = 0 if is_num else 1\n",
    "            for v in range(low_v, max_v + 1):\n",
    "                res += func(\n",
    "                    s,\n",
    "                    i+1,\n",
    "                    cntd + (v==d),\n",
    "                    is_limit and (v==max_v),\n",
    "                    True \n",
    "                )\n",
    "            return res \n",
    "        \n",
    "        lowcount = 0\n",
    "        for c in slow:\n",
    "            if c == str(d):\n",
    "                lowcount += 1\n",
    "\n",
    "        return func(shigh, 0, 0, True, False) - func(slow, 0, 0, True, False) + lowcount"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
